
//求解背包问题的关键是求出它的状态转移方程
//两层循环，第一次的for是商品的个数，第二次for是背包的容量。然后k数组中的每次的数据k[i]的key其实是商品的尺寸，
//value是商品的价值，每次遇到新的商品就和之前的总价比较，
//看”有没有必要“放入。之后一旦接受了新的商品，就暂存入数组，之后倒叙序便可以获取到相应的商品值了

//部分背包 即物品可以分开只装入一部分 可以用贪心算法求解

//0-1背包 物品只有一个 只存在装与不装的状态 用动态规划求解

//完全背包 物品有无限个 可以随意选取  用动态规划求解

//动态方程分别为：
//0-1背包问题：B[i][j] = B[i-1][j]，其中j < W[i]；或者B[i][j] = max(B[i-1][j], B[i-1][j-W[i]] + P[i])，其中j >= W[i]。
//完全背包问题：B[i][j] = B[i-1][j]，其中j < W[i]；或者B[i][j] = max(B[i-1][j], B[i][j-W[i]] + P[i])，其中j >= W[i]。
//0-1背包解法
function packageMaxValue(weight, value, size) {
  // 省略参数合法性校验
  let bagMatrix = []
  for (let w = 0; w <= size; w++) {
    // js不能直接创建二维数组，所以在此初始化数组
    bagMatrix[w] = []
    for (let j = 0; j < 5; j++) {
      // 背包的容量为0，那么一个东西也装不下，此时的值肯定也是为0
      if (w === 0) {
        bagMatrix[w][j] = 0
        continue
      }
      // 背包的容量小于物品j的重量，那么就没有上述情况a了
      if (w < weight[j]) {
        bagMatrix[w][j] = bagMatrix[w][j - 1] || 0
        continue
      }
      bagMatrix[w][j] = Math.max((bagMatrix[w - weight[j]][j] || 0) + value[j], bagMatrix[w][j - 1] || 0)
    }
  }
  return bagMatrix
}

let weight = [4, 5, 6, 2, 6]
let value = [6, 4, 5, 3, 6]

console.log(packageMaxValue(weight, value, 9))
